home *** CD-ROM | disk | FTP | other *** search
/ NeXT Education Software Sampler 1992 Fall / NeXT Education Software Sampler 1992 Fall.iso / Programming / c-runtime / dispatch / hash.h < prev    next >
Encoding:
C/C++ Source or Header  |  1992-08-18  |  13.6 KB  |  286 lines
  1. /* -*-c-*- */
  2.  
  3. /* Copyright (C) 1989, 1992 Free Software Foundation, Inc.
  4.  
  5. This file is part of GNU CC.
  6.  
  7. GNU CC is free software; you can redistribute it and/or modify
  8. it under the terms of the GNU General Public License as published by
  9. the Free Software Foundation; either version 2, or (at your option)
  10. any later version.
  11.  
  12. GNU CC is distributed in the hope that it will be useful,
  13. but WITHOUT ANY WARRANTY; without even the implied warranty of
  14. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15. GNU General Public License for more details.
  16.  
  17. You should have received a copy of the GNU General Public License
  18. along with GNU CC; see the file COPYING.  If not, write to
  19. the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  20.  
  21. /* As a special exception, if you link this library with files
  22.    compiled with GCC to produce an executable, this does not cause
  23.    the resulting executable to be covered by the GNU General Public License.
  24.    This exception does not however invalidate any other reasons why
  25.    the executable file might be covered by the GNU General Public License.  */
  26.  
  27. /* 
  28.   $Header: /usr/user/dennis_glatting/ObjC/c-runtime/dispatch/RCS/hash.h,v 0.10 1992/08/18 04:46:58 dglattin Exp $
  29.   $Author: dglattin $
  30.   $Date: 1992/08/18 04:46:58 $
  31.   $Log: hash.h,v $
  32.  * Revision 0.10  1992/08/18  04:46:58  dglattin
  33.  * Saving a working version before release.
  34.  *
  35.  * Revision 0.9  1992/04/13  11:43:08  dennisg
  36.  * Check in after array version of run-time works.
  37.  * Expect more changes as hash version and other changes are made.
  38.  *
  39.  * Revision 0.8  1991/12/10  12:05:28  dennisg
  40.  * Cleaned up file format for a distribution.
  41.  *
  42.  * Revision 0.7  1991/12/03  02:01:23  dennisg
  43.  * fixed assert macro.
  44.  * added memory allocation adjustment macro for hash size allocation.
  45.  *
  46.  * Revision 0.6  1991/11/24  01:20:02  dennisg
  47.  * changed shorts back to ints.
  48.  * the efficiency gained didn't out weight the grossness of the code.
  49.  *
  50.  * Revision 0.5  1991/11/23  22:19:21  dennisg
  51.  * converted some entries in the hash structure from ints to shorts.
  52.  * this was done to use a less expensive division instruction
  53.  * in the hashIndex () routine.
  54.  *
  55.  * Revision 0.4  1991/11/21  22:25:19  dennisg
  56.  * deleted hash mask information from hash struct.
  57.  * changed hashing algorithm.  those values are no longer needed.
  58.  *
  59.  * Revision 0.3  1991/11/07  23:23:40  dennisg
  60.  * implemented hash table expansion as suggested by rms.
  61.  *
  62.  * Revision 0.2  1991/11/07  22:30:54  dennisg
  63.  * added copyleft
  64.  *
  65.  * Revision 0.1  1991/10/24  00:45:39  dennisg
  66.  * Initial check in.  Preliminary development stage.
  67.  *
  68. */
  69.  
  70.  
  71. #ifndef _hash_INCLUDE_GNU
  72. #define _hash_INCLUDE_GNU
  73.  
  74.                                                 /* If someone is using a c++
  75.                                                   compiler then adjust the 
  76.                                                   types in the file back 
  77.                                                   to C. */
  78. #ifdef __cplusplus
  79. extern "C" {
  80. #endif
  81.  
  82. #include        <assert.h>
  83. #include  <sys/types.h>
  84.  
  85. #include        <mutex.h>
  86.  
  87. /*
  88.  * This data structure is used to hold items
  89.  *  stored in a hash table.  Each node holds 
  90.  *  a key/value pair.
  91.  *
  92.  * Items in the cache are really of type void*.
  93.  */
  94. typedef struct cache_node {
  95.   struct cache_node*  nextNode;                   /* Pointer to next entry on
  96.                                                     the list.  NULL indicates
  97.                                                     end of list. */
  98.   void*               theKey;                     /* Key used to locate the
  99.                                                     value.  Used to locate
  100.                                                     value when more than one
  101.                                                     key computes the same hash
  102.                                                     value. */
  103.   void*               theValue;                   /* Value stored for the
  104.                                                     key. */
  105. } CacheNode, *CacheNode_t;
  106.  
  107.  
  108. /*
  109.  * This data type is the function that computes a hash code given a key.
  110.  * Therefore, the key can be a pointer to anything and the function specific
  111.  * to the key type. 
  112.  *
  113.  * Unfortunately there is a mutual data structure reference problem with this
  114.  * typedef.  Therefore, to remove compiler warnings the functions passed to
  115.  * hash_new() will have to be casted to this type. 
  116.  */
  117. typedef u_int   (*HashFunc)(void*, void*);
  118.  
  119. /*
  120.  * This data type is the function that compares two hash keys and returns an
  121.  * integer greater than, equal to, or less than 0, according as the first
  122.  * parameter is lexico-graphically greater than, equal to, or less than the
  123.  * second. 
  124.  */
  125.  
  126. typedef int     (*CompareFunc)(void*, void*);
  127.  
  128.  
  129. /*
  130.  * This data structure is the cache.
  131.  *
  132.  * It must be passed to all of the hashing routines
  133.  *   (except for new).
  134.  */
  135. typedef struct cache {
  136.   /*
  137.    * Variables used to implement the
  138.    *  hash itself.
  139.    */
  140.   CacheNode_t  (* theNodeTable)[];                /* Pointer to an array of
  141.                                                     hash nodes. */
  142.   /*
  143.    * Variables used to track the size of the hash
  144.    *  table so to determine when to resize it.
  145.    */
  146.   u_int       sizeOfHash,                        /* Number of buckets 
  147.                                                     allocated for the hash
  148.                                                     table  (number of array
  149.                                                     entries allocated for
  150.                                                     "theNodeTable").  Must be
  151.                                                     a power of two. */
  152.               entriesInHash,                      /* Current number of entries
  153.                                                     in the hash table. */
  154.                                                         mask;                                                                                                                           /* Precomputed mask. */
  155.   /*
  156.    * Variables used to implement indexing
  157.    *  through the hash table.
  158.    */
  159.   u_int       lastBucket;                         /* Tracks which entry in the
  160.                                                     array where the last value
  161.                                                     was returned. */
  162.                                                                                                                                                                                                         /* Function used to compute
  163.                                                                                                                                                                                                                 a hash code given a key. 
  164.                                                                                                                                                                                                                 This function is specified 
  165.                                                                                                                                                                                                                 when the hash table is 
  166.                                                                                                                                                                                                                 created. */
  167.         HashFunc                hashFunc;
  168.                                                                                                                                                                                                         /* Function used to compare 
  169.                                                                                                                                                                                                                 two hash keys to determine
  170.                                                                                                                                                                                                                 if they are equal. */
  171.         CompareFunc     compareFunc;
  172. } Cache, *Cache_t;
  173.  
  174.  
  175.                                                 /* Prototypes for hash
  176.                                                   functions. */
  177.                                                 /* Allocate and initialize 
  178.                                                   a hash table. */ 
  179. Cache_t 
  180. hash_new (u_int sizeOfHash, HashFunc aHashFunc, CompareFunc aCompareFunc);
  181.                                                 /* Deallocate all of the
  182.                                                   hash nodes and the cache
  183.                                                   itself. */
  184. void 
  185. hash_delete (Cache_t theCache);
  186.                                                 /* Add the key/value pair
  187.                                                   to the hash table.  If the
  188.                                                   hash table reaches a 
  189.                                                   level of fullnes then
  190.                                                   it will be resized. 
  191.                                                    
  192.                                                   assert() if the key is 
  193.                                                   already in the hash. */
  194. void 
  195. hash_add (Cache_t* theCache, void* aKey, void* aValue);
  196.                                                 /* Remove the key/value pair
  197.                                                   from the hash table.  
  198.                                                   assert() if the key isn't 
  199.                                                   in the table. */
  200. void 
  201. hash_remove (Cache_t theCache, void* aKey);
  202.                                                 /* Used to index through the
  203.                                                   hash table.  Start with NULL
  204.                                                   to get the first entry.
  205.                                                   
  206.                                                   Successive calls pass the
  207.                                                   value returned previously.
  208.                                                   ** Don't modify the hash
  209.                                                   during this operation *** 
  210.                                                   
  211.                                                   Cache nodes are returned
  212.                                                   such that key or value can
  213.                                                   ber extracted. */
  214. CacheNode_t 
  215. hash_next (Cache_t theCache, CacheNode_t aCacheNode);
  216.  
  217.                                                                                                                                                                                                 /* Used to return a value from 
  218.                                                                                                                                                                                                         a hash table using a given 
  219.                                                                                                                                                                                                         key.  */
  220. void* 
  221. hash_value_for_key (Cache_t theCache, void* aKey);
  222.  
  223.  
  224. /************************************************
  225.  
  226.         Useful hashing functions.  
  227.         
  228.         Declared inline for your pleaseure. 
  229.         
  230. ************************************************/
  231.  
  232.                                                 /* Calculate a hash code by 
  233.                                                                                                                                                                                                         performing some manipulation 
  234.                                                                                                                                                                                                         of the key pointer. */
  235. static inline u_int 
  236. intHash(Cache_t theCache, void* aKey) {
  237.  
  238.  
  239.   assert(sizeof (u_int) == sizeof (aKey));
  240.  
  241.         return ((u_int)aKey >> (sizeof(void*) - 1)) & theCache->mask ;
  242. }
  243.  
  244.                                                 /* Calculate a hash code by 
  245.                                                                                                                                                                                                         iterating over a NULL 
  246.                                                                                                                                                                                                         terminate string. */
  247. static inline u_int 
  248. strHash(Cache_t theCache, void* aKey) {
  249.  
  250.         u_int   ret = 0;
  251.         u_int   ctr = 0;
  252.         
  253.         
  254.         while(*(char*)aKey) {
  255.                 ret ^= *(char*)aKey++ << ctr;
  256.                 ctr = (ctr + 1) % sizeof(void*);
  257.         }
  258.  
  259.         return ret & theCache->mask ;
  260. }
  261.  
  262.  
  263.                                                                                                                                                                                                 /* Compare two integers. */
  264. static inline int 
  265. intCmp(void* k1, void* k2) {
  266.  
  267.  
  268.         return !((int)k1 - (int)k2);
  269. }
  270.  
  271.  
  272.                                                                                                                                                                                                 /* Compare two strings. */
  273. static inline int 
  274. strCmp(void* k1, void* k2) {
  275.  
  276.  
  277.         return !strcmp( k1, k2 );
  278. }
  279.  
  280.  
  281. #ifdef __cplusplus
  282. }
  283. #endif
  284.  
  285. #endif
  286.